package com.yanceysong.codetop.s21_s30;

/**
 * @ClassName S30_Hard_42_接雨水
 * @Description
 * @date 2025/09/16
 * @Author yanceysong
 * @Version 1.0
 */
public class S30_Hard_42_接雨水 {

    /**
     * S30_Hard_42_接雨水
     * <p>
     * LeetCode：
     * <a href="https://leetcode.cn/problems/trapping-rain-water/">...</a>
     * <p>
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * <p>
     * 示例 1：
     * <p>
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     * <p>
     * 示例 2：
     * <p>
     * 输入：height = [4,2,0,3,2,5]
     * 输出：9
     * <p>
     * 提示：
     * <p>
     * n == height.length
     * 1 <= n <= 2 * 10^4
     * 0 <= height[i] <= 10^5
     * <p>
     * 使用双指针法计算接雨水问题
     * <p>
     * 算法原理：
     * 对于任意位置i，能积水的高度 = min(左侧最高柱子, 右侧最高柱子) - 当前柱子高度
     * 双指针优化：从两端向中间移动，始终处理较矮一侧的柱子
     * <p>
     * 核心思想：
     * 1. 维护左右两个指针和对应的最大高度
     * 2. 比较当前左右指针位置的高度
     * 3. 处理较矮的一侧（因为积水高度由较矮一侧决定）
     * 4. 更新最大高度并计算积水量
     * <p>
     * 为什么可以只考虑一侧？
     * - 当 height[left] < height[right] 时，左侧的积水高度只取决于左侧的最大值
     * - 因为右侧已经有更高的柱子，所以左侧的积水不会被右侧限制
     * - 反之亦然
     * <p>
     * 图解示例：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * <p>
     * 正确柱子高度图（最高=3，两个字符为一列，█ 表示柱子）：
     * <p>
     * 层3:         ░  ░  ░  ░  ░  ░  ░  █  ░  ░  ░  ░
     * 层2:         ░  ░  ░  █  ░  ░  ░  █  █  ░  █  ░
     * 层1:         ░  █  ░  █  █  ░  █  █  █  █  █  █
     * 索引:        0  1  2  3  4  5  6  7  8  9 10 11
     * 高度:        0  1  0  2  1  0  1  3  2  1  2  1
     * 说明：上面用 ░ 代表空；视觉对齐与运行时 printHeightVisualization 输出一致（只是不打印空格）。
     * <p>
     * 积水示意（~ 表示水；水显示在能盛水的最低一层）：
     * 层3:         ░  ░  ░  ░  ░  ░  ░  █  ░  ░  ░  ░
     * 层2:         ░  ░  ░  █  ~  ~  ~  █  █  ~  █  ░
     * 层1:         ░  █  ~  █  █  ~  █  █  █  █  █  █
     * 水量列:       0  0  1  0  1  2  1  0  0  1  0  0  (总计=6)
     * 各索引积水：2 -> 1, 4 -> 1, 5 -> 2, 6 -> 1, 9 -> 1
     * <p>
     * 双指针移动过程（只展示前几步）：
     * 初始：left=0,h=0; right=11,h=1; leftMax=0; rightMax=0
     * Step1: 处理左侧(0<1) 水=0  left=1  leftMax=0
     * Step2: 比较 left=1(1) 与 right=11(1) 处理右侧  rightMax=1 水=0 right=10
     * Step3: 比较 1(1) 与 10(2) 处理左侧 leftMax=1 水=0 left=2
     * Step4: left=2(0) < right=10(2) leftMax=1 水=1 (index2) 累计=1 left=3
     * ... 继续直到相遇，累计=6
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public int trap(int[] height) {
        // 边界条件检查
        if (height == null || height.length <= 2) {
            return 0;  // 少于3个柱子无法形成积水
        }

        int totalWaterTrapped = 0;  // 总积水量

        // 双指针：分别从数组两端开始
        int leftPointer = 0;                    // 左指针
        int rightPointer = height.length - 1;   // 右指针

        // 记录左右两侧遇到的最大高度
        int leftMaxHeight = 0;   // 左侧最大高度
        int rightMaxHeight = 0;  // 右侧最大高度

        // 当左右指针还未相遇时继续处理
        while (leftPointer < rightPointer) {
            // 更新左右两侧的最大高度
            leftMaxHeight = Math.max(leftMaxHeight, height[leftPointer]);
            rightMaxHeight = Math.max(rightMaxHeight, height[rightPointer]);

            // 比较左右指针位置的高度，处理较矮的一侧
            if (height[leftPointer] < height[rightPointer]) {
                int currentWater = leftMaxHeight - height[leftPointer]; // 当前位置积水
                totalWaterTrapped += currentWater;
                leftPointer++;
            } else {
                int currentWater = rightMaxHeight - height[rightPointer]; // 当前位置积水
                totalWaterTrapped += currentWater;
                rightPointer--;
            }
        }

        return totalWaterTrapped;
    }

    public static void main(String[] args) {
        S30_Hard_42_接雨水 solution = new S30_Hard_42_接雨水();

        System.out.println("=== 接雨水算法测试开始 ===");

        // 测试1: 题目示例1 - [0,1,0,2,1,0,1,3,2,1,2,1]
        System.out.println("\n--- 测试1: 经典示例 [0,1,0,2,1,0,1,3,2,1,2,1] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - [4,2,0,3,2,5]
        System.out.println("\n--- 测试2: 简单示例 [4,2,0,3,2,5] ---");
        testCase2(solution);

        // 测试3: 边界情况 - 空数组
        System.out.println("\n--- 测试3: 空数组 ---");
        testEmptyArray(solution);

        // 测试4: 边界情况 - 单个元素
        System.out.println("\n--- 测试4: 单个元素 [5] ---");
        testSingleElement(solution);

        // 测试5: 边界情况 - 两个元素
        System.out.println("\n--- 测试5: 两个元素 [3,1] ---");
        testTwoElements(solution);

        // 测试6: 递增序列
        System.out.println("\n--- 测试6: 递增序列 [1,2,3,4,5] ---");
        testIncreasingSequence(solution);

        // 测试7: 递减序列
        System.out.println("\n--- 测试7: 递减序列 [5,4,3,2,1] ---");
        testDecreasingSequence(solution);

        // 测试8: 相同高度
        System.out.println("\n--- 测试8: 相同高度 [3,3,3,3,3] ---");
        testSameHeight(solution);

        // 测试9: U型结构
        System.out.println("\n--- 测试9: U型结构 [3,0,2,0,4] ---");
        testUShapeStructure(solution);

        // 测试10: 复杂山峰结构
        System.out.println("\n--- 测试10: 复杂山峰 [5,2,1,2,1,5] ---");
        testComplexMountain(solution);

        // 测试11: 零高度柱子
        System.out.println("\n--- 测试11: 包含零高度 [0,0,0] ---");
        testAllZeros(solution);

        // 测试12: 大数值测试
        System.out.println("\n--- 测试12: 大数值测试 ---");
        testLargeValues(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 测试经典示例：[0,1,0,2,1,0,1,3,2,1,2,1]
     * 正确积水分布：
     * index 2  ->  1
     * index 4  ->  1
     * index 5  ->  2
     * index 6  ->  1
     * index 9  ->  1
     * 合计 6
     */
    private static void testCase1(S30_Hard_42_接雨水 solution) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println("输入数组: " + arrayToString(height));
        printHeightVisualization(height);

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 6)");
        assert result == 6 : "期望积水量为6";
        System.out.println("✓ 经典示例测试通过");
    }

    /**
     * 测试简单示例：[4,2,0,3,2,5]
     */
    private static void testCase2(S30_Hard_42_接雨水 solution) {
        int[] height = {4, 2, 0, 3, 2, 5};
        System.out.println("输入数组: " + arrayToString(height));
        printHeightVisualization(height);

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 9)");
        assert result == 9 : "期望积水量为9";
        System.out.println("✓ 简单示例测试通过");
    }

    /**
     * 测试空数组边界情况
     */
    private static void testEmptyArray(S30_Hard_42_接雨水 solution) {
        int[] height = {};
        System.out.println("输入数组: []");

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 0)");
        assert result == 0 : "空数组应该返回0";
        System.out.println("✓ 空数组测试通过");
    }

    /**
     * 测试单个元素
     */
    private static void testSingleElement(S30_Hard_42_接雨水 solution) {
        int[] height = {5};
        System.out.println("输入数组: " + arrayToString(height));

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 0)");
        assert result == 0 : "单个元素无法形成积水";
        System.out.println("✓ 单个元素测试通过");
    }

    /**
     * 测试两个元素
     */
    private static void testTwoElements(S30_Hard_42_接雨水 solution) {
        int[] height = {3, 1};
        System.out.println("输入数组: " + arrayToString(height));

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 0)");
        assert result == 0 : "两个元素无法形成积水";
        System.out.println("✓ 两个元素测试通过");
    }

    /**
     * 测试递增序列：无法积水
     */
    private static void testIncreasingSequence(S30_Hard_42_接雨水 solution) {
        int[] height = {1, 2, 3, 4, 5};
        System.out.println("输入数组: " + arrayToString(height));

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 0)");
        assert result == 0 : "递增序列无法积水";
        System.out.println("✓ 递增序列测试通过");
    }

    /**
     * 测试递减序列：无法积水
     */
    private static void testDecreasingSequence(S30_Hard_42_接雨水 solution) {
        int[] height = {5, 4, 3, 2, 1};
        System.out.println("输入数组: " + arrayToString(height));

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 0)");
        assert result == 0 : "递减序列无法积水";
        System.out.println("✓ 递减序列测试通过");
    }

    /**
     * 测试相同高度：无法积水
     */
    private static void testSameHeight(S30_Hard_42_接雨水 solution) {
        int[] height = {3, 3, 3, 3, 3};
        System.out.println("输入数组: " + arrayToString(height));

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 0)");
        assert result == 0 : "相同高度无法积水";
        System.out.println("✓ 相同高度测试通过");
    }

    /**
     * 测试U型结构：[3,0,2,0,4]
     * 正确积水：index1=3, index2=1, index3=3  ->  总计 7
     */
    private static void testUShapeStructure(S30_Hard_42_接雨水 solution) {
        int[] height = {3, 0, 2, 0, 4};
        System.out.println("输入数组: " + arrayToString(height));
        printHeightVisualization(height);

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 7)");
        assert result == 7 : "U型结构期望积水7个单位";
        System.out.println("✓ U型结构测试通过");
    }

    /**
     * 测试复杂山峰结构：[5,2,1,2,1,5]
     */
    private static void testComplexMountain(S30_Hard_42_接雨水 solution) {
        int[] height = {5, 2, 1, 2, 1, 5};
        System.out.println("输入数组: " + arrayToString(height));
        printHeightVisualization(height);

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 14)");
        assert result == 14 : "复杂山峰期望积水14个单位";
        System.out.println("✓ 复杂山峰测试通过");
    }

    /**
     * 测试全零数组
     */
    private static void testAllZeros(S30_Hard_42_接雨水 solution) {
        int[] height = {0, 0, 0, 0, 0};
        System.out.println("输入数组: " + arrayToString(height));

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 0)");
        assert result == 0 : "全零数组无法积水";
        System.out.println("✓ 全零数组测试通过");
    }

    /**
     * 测试大数值
     */
    private static void testLargeValues(S30_Hard_42_接雨水 solution) {
        int[] height = {100000, 0, 0, 0, 100000};
        System.out.println("输入数组: " + arrayToString(height));

        int result = solution.trap(height);
        System.out.println("trap()  ->  " + result + " (期望: 300000)");
        assert result == 300000 : "大数值测试期望积水300000个单位";
        System.out.println("✓ 大数值测试通过");
    }

    /**
     * 辅助方法：将数组转换为字符串表示
     */
    private static String arrayToString(int[] arr) {
        if (arr.length == 0) return "[]";

        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    /**
     * 辅助方法：可视化高度图（简化版）
     */
    private static void printHeightVisualization(int[] height) {
        if (height.length == 0) return;

        int maxHeight = 0;
        for (int h : height) {
            maxHeight = Math.max(maxHeight, h);
        }

        System.out.println("高度图可视化:");
        for (int level = maxHeight; level > 0; level--) {
            for (int j : height) {
                if (j >= level) {
                    System.out.print("█ ");
                } else {
                    System.out.print("  ");
                }
            }
            System.out.println();
        }

        // 打印索引
        for (int i = 0; i < height.length; i++) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
